%!TEX TS-program = xelatex
%!TEX encoding = UTF-8 Unicode

\documentclass[10pt, fleqn]{article}
\usepackage{amsmath}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage{lastpage}
\usepackage{multicol}

% DOCUMENT LAYOUT
\usepackage{geometry} 
\geometry{letterpaper, textwidth=6in, textheight=9in}
\setlength{\parindent}{0in}

% SECTION HEADINGS
\usepackage{sectsty}
\sectionfont{\mdseries}

% ITEM ENVIRONMENT
\newenvironment{baseenumerate}
  {\begin{enumerate}[leftmargin=0pt]
	\setlength{\baselineskip}{0pt}
	\setlength{\itemsep}{0pt}
	\setlength{\parskip}{10pt}}
  {\end{enumerate}}
	
\newenvironment{myenumerate}
  {\begin{enumerate}[leftmargin=*]
	\setlength{\baselineskip}{0pt}
    \setlength{\itemsep}{0pt}
	\setlength{\parskip}{10pt}}
  {\end{enumerate}}

\renewcommand{\labelenumi}{\textbf{Problem \arabic{enumi}.}}
\renewcommand{\labelenumii}{\arabic{enumii}.}
\renewcommand{\labelenumiii}{\roman{enumiii}.}

% PAGE NUMBERS
\usepackage{fancyhdr}
\pagestyle{fancy}
\cfoot{}
\rfoot{\textbf{\thepage} / \pageref{LastPage}}
\renewcommand{\headrulewidth}{0pt}

% DOCUMENT
\begin{document}

\begin{multicols}{2}
  \textbf{Assignment 2.}
  \columnbreak
  
  \begin{flushright}
	Benedict Yip \\
	March 1, 2011 \\
	CS 378
  \end{flushright}
\end{multicols}

\begin{flushleft}
  
  \begin{baseenumerate}

  \item % Problem 1.
    Matrix-matrix multiplication (MMM) has differing cache miss ratio given varying loop orders.

    These following graph details the cache miss ratio for matrix-matrix multiplication calculations of various matrix sizes on the Intel Nehalem architecture, which has a 256KB L2 cache, with 8-way, 64B cache lines:

    \begin{figure}[h]
      \begin{center}
        \includegraphics[scale=0.5]{1.png}
        \caption{Cache miss ratios for matrix-matrix multiplication.}
      \end{center}
    \end{figure}

    From the graph, we see that there are three equivalence classes pertaining to loop orders: $\{ijk, jik\}, \{jki, kji\}, \{ikj, kij\}$. These equivalence classes are given from whichever index is the innermost loop. By examining our matrix-matrix multiply, we can determine which loop orders exhibit which types of locality for certain matrices.

    A matrix-matrix multiply algorithm is given for the problem $A \cdot B = C$:
    
    \begin{tabbing}
		For \= $i = 1..n$ \\
		    \> For \= $j = 1..n$ \\
            \>     \> For \= $k = 1..n$ \\
            \>     \>     \> $C_{ij} = C_{ij} + A_{ik} \cdot B_{kj}$
	\end{tabbing}

    As detailed in class, by examining different permutations of the above algorithm, we see that the \textit{k}-equivalence class exhibits some spatial and temporal locality; the \textit{i}-equivalence class, little temporal locality and no spatial locality; and the \textit{j}-equivalence class, good spatial and temporal locality. This is expressed in the graph by the varying cache miss ratios, which in turn are dependent on the capacity and line size of the cache ($C = 32000, b = 8$).

    The measurements given in the graph vary widely with analytical formulas derived in class, even taking into account the different cache specifications. This is due to the amount of conflict misses, giving us the following formulas for small cache scenarios.

    \textit{k}-equivalence class: $\frac{0.5(b+1)}{b} = 0.5625$. \\
    \textit{i}-equivalence class: $1$. \\
    \textit{j}-equivalence class: $\frac{0.5}{b} = 0.0625$.

    These calculations are verified in the above graph.

  \item % Problem 2.
    \begin{myenumerate}
      
    \item % 1.
      For the wavefront algorithm over a matrix stored in column-major order, we have the following miss ratios:

      \textbf{Large cache.} For a large cache scenario, there are only cold misses. The size of the data is $n^2$ and there are $3n^2$ data accesses. Each miss brings in $b$ floating-point numbers. Thus, we have a miss ratio = $\frac{n^2}{3b(n-1)^2} \approx \frac{n^2}{3bn^2} = \frac{1}{3b}$.

      \textbf{Small cache.} For the small cache scenario, we must take into account both cold and capacity misses. We can see that there will be $\frac{n^2}{b}$ cold misses. Because the matrix is in column-major order, there are $2n^2$ capacity misses, as there is no spatial nor temporal locality. Thus, we have a miss ratio of $\frac{2b+1}{3b}$.

    \item % 2.
      In order to prevent any capacity misses, we would need a cache that is able to hold $n^2$ floating-point numbers. Thus, $n = \sqrt{C}$.

    \item % 3.
      For the wavefront algorithm over a matrix stored in row-major order, we have the following miss ratios:

      \textbf{Large cache.} This is the same as in the column-major order.

      \textbf{Small cache.} For the small cache scenario, we must take into account both cold and capacity misses. We can see that there will be $\frac{n^2}{b}$ cold misses. Because the matrix is in row-major order, there are $\frac{n^2}{b}$ capacity misses, as there is locality exhibited. Thus, we have a miss ratio of $\frac{2}{3b}$.

      The jump for LRU replacement policy is the same as in the column-major ordering.

    \item

      Yes, the following graph shows that miss ratios agree with the above calculations:

      \includegraphics[scale=0.5]{2.png}
      
    \end{myenumerate}
  
  \end{baseenumerate}
\end{flushleft}

\end{document}
